package week07

// 130. 被围绕的区域
// https://leetcode-cn.com/problems/surrounded-regions/

func solve(board [][]byte) {
	var m, n = len(board), len(board[0])

	index := func(x, y int) int {
		return x * n + y
	}

	var father = make([]int, m*n+1)
	for i := range father {
		father[i] = i
	}

	for x := range board {
		for y := range board[x] {
			if board[x][y] == 'X' {
				continue
			}
			for dir := range dx {
				nx := x + dx[dir]
				ny := y + dy[dir]
				if nx < 0 || ny < 0 || nx >= len(board) || ny >= len(board[nx]) {
					unionSet(father, m*n, index(x, y))
				} else if board[nx][ny] == 'O' {
					unionSet(father, index(x, y), index(nx, ny))
				}
			}
		}
	}

	for x := range board {
		for y := range board[x] {
			if board[x][y] != 'X' && find(father, index(x, y)) != father[m*n] {
				board[x][y] = 'X'
			}
		}
	}
}

func find(father []int, x int) int {
	if father[x] != x {
		father[x] = find(father, father[x])
	}
	return father[x]
}

func unionSet(father []int, x, y int) {
	father[find(father, y)] = find(father, x)
}


var dx = [4]int{0, 1, 0, -1}
var dy = [4]int{1, 0, -1, 0}